package q124_maxPathSum;

import CommonClass.Common.TreeNode;

public class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    /*
    对于maxGain 实际上计算的是对于每一个节点 其 左或者右 两条路径中最大的贡献值 加上该节点的值
    因此其实际上只包含了一条路径 而答案必然是由 root 节点 左侧最大贡献 加 root最大贡献（root不一定被选） 加 右侧最大贡献构成
    所以我们在递归中就更新答案
    关键在于 递归一定要先到达子节点 然后向上计算 才能更新到最大值
     */
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);


        // 答案的更新关键在于下面的两条语句
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;
        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }

}
